//题目:
// 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
    int ret=0;
    int kk;
public:
    void dfs(const vector<int>& prices,int pos,int flag,int money,int count)
    {
        //进入该函数时，表示在第pos天，已经交易count次，赚取利润为money。
        //flag==1，表示“买入”状态；flag==0，表示“卖出”状态
        ret=max(ret,money);

        //交易count次 || 到了最后一天，则不再交易
        if(count==kk || pos==prices.size()-1) return;
        //买入状态
        if(flag==1)
        {
            for(int i=pos+1;i<prices.size();i++)
                if(prices[i]>prices[pos])
                    dfs(prices,i,0,money+prices[i],count+1);//把股票卖出
        }
        //卖出状态
        else
        {
            for(int i=pos+1;i<prices.size();i++)
                dfs(prices,i,1,money-prices[i],count);//买股票
        }
    }
    int maxProfit(int k,vector<int>& prices) 
    {
        // 全排列————超时
        // kk=k;
        // for(int i=0;i<prices.size();i++)
        //     dfs(prices,i,1,0-prices[i],0);//第i天买入股票，交易次数为[0,k]时，最后一天赚取的最大利润
        // return ret;

        //动态规划 ———— 第i天结束后，有两种状态:“买入”[交易次数]、“卖出”[交易次数]
        //1.创建dp细化表
        int n=prices.size();
        vector<vector<int>> f(n,vector<int>(k+1));//第i天结束后，交易j次，处于"买入"状态，获取的最大利润
        vector<vector<int>> g(n,vector<int>(k+1));//第i天结束后，交易j次，处于"卖出"状态，获取的最大利润
        //动态转移方程: f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
        //             g[i][j]=max(g[i-1][j],f[i-1][j-1]+prices[i]);
        //2.初始化
        f[0][0]=0-prices[0],g[0][0]=0;
        for(int j=1;j<=k;j++)
        {
            f[0][j]=-0x3f3f3f3f;
            g[0][j]=-0x3f3f3f3f;
        }

        //3.填表
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=k;j++)
            {
                f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
                if(j-1<0)
                    g[i][j]=g[i-1][j];
                else
                    g[i][j]=max(g[i-1][j],f[i-1][j-1]+prices[i]);
            }
        }
        //4.确定返回值
        int ret=0;
        for(int j=0;j<=k;j++)
            ret=max(ret,g[n-1][j]);
        return ret;
    }
};